package com.kobeliu.entity;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/3 10:52
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
 * 示例 1：
 *
 * 输入：nums = [3,4,3,3]
 * 输出：4
 *
 * 示例 2：
 *
 * 输入：nums = [9,1,7,9,7,9,7]
 * 输出：1
 *
 */
public class Demo_65_sword_56_2 {

    public static void main(String[] args) {
        int[] nums = new int[]{3,12,3,3,7,7,7,8,8,8};
        System.out.println(singleNumber(nums));
    }

    /**
     * 使用hashMap 很垃圾的算法，改进看不懂 妈的
     * @param nums
     * @return
     */
    public static int singleNumber1(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }

        for(Map.Entry<Integer,Integer> e:map.entrySet()){
            if(e.getValue()==1){
                return e.getKey();
            }
        }
        return 0;
    }

    /**
     * 用位运算更慢了 用的不到家
     * @param nums
     * @return
     */
    public static int singleNumber(int[] nums) {
        int[] bit = new int[32];
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            int j = 0;
            while(nums[i]!=0){
                if((nums[i]&1)!=0){
                    bit[j] = bit[j]+1;
                }
                //
                nums[i] /= 2;
                j++;
            }
        }
        len = 0; //len --> sum
        for(int i=0;i<32;i++){
            if((bit[i]%3)!=0){
                len += (bit[i]%3)*Math.pow(2,i);
            }
        }

        return len;
    }




}
